/**********************************************************

@description:no recursion preorder full down stack
*File Name:binary_tree_no_pre.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Sat 26 Apr 2025 04:43:16 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct tnode{
	char data;
	struct tnode* lchild;
	struct tnode* rchild;
	unsigned char flag:1;
}tnode;
typedef struct stack{
	void *arr[MAXSIZE];
	unsigned short sp;//stack pointer
}stack;
typedef void (*visit)(tnode*);

stack *init_s(){
	stack *s=(stack*)malloc(sizeof(stack));
	s->sp=MAXSIZE;
	return s;
}
int isEmpty(stack *s){
	return s->sp==MAXSIZE;
}
int isFull(stack *s){
	return s->sp==0;
}
void push(stack *s,void *data){
	if(!data){
		return;
	}
	if(isFull(s)){
		printf("stack full,push failed!\n");
		return;
	}
	s->arr[--(s->sp)]=data;
}
void* pop(stack *s){
	if(isEmpty(s)){
	//	printf("stack empty,pop failed!\n");
		return NULL;
	}
	return s->arr[(s->sp)++];
}
void* getTop(stack *s){
	if(isEmpty(s)){
		return NULL;
	}
	return s->arr[(s->sp)];
}
void preorder(tnode* t,visit v){
	v(t);
	if(t){
		preorder(t->lchild,v);
		preorder(t->rchild,v);
	}
}
void inorder(tnode* t,visit v){
	if(t){
		inorder(t->lchild,v);
		v(t);
		inorder(t->rchild,v);
	}
}
void postorder(tnode* t,visit v){
	if(t){
		postorder(t->lchild,v);
		postorder(t->rchild,v);
		v(t);
	}
}
void nopreorder(tnode *t,visit v){
	tnode *cur=t;
	stack *s=init_s();
	while(cur){
		v(cur);
		push(s,cur);
		cur=cur->lchild;
	}
	while(cur=pop(s)){
		if(!cur->rchild)
			continue;
		cur=cur->rchild;
		while(cur){
			v(cur);
			push(s,cur);
			cur=cur->lchild;
		}
	}
}
void nopreorder1(tnode *t,visit v){
	tnode *cur=t;
	stack  *s=init_s();
	while(cur || !isEmpty(s)){
		if(cur){
			v(cur);
			push(s,cur);
			cur=cur->lchild;
		}else{
			cur=pop(s);
			cur=cur->rchild;
		}
	}
}
void noinorder(tnode *t,visit v){
	stack *s= init_s();
	tnode *cur=NULL;
	push(s,t);
	cur=t->lchild;
	while(cur){
		push(s,cur);
		cur=cur->lchild;
	}
	while(cur=pop(s)){
		v(cur);
		cur=cur->rchild;
		while(cur){
			push(s,cur);
			cur=cur->lchild;
		}
	}
}

void noinorder1(tnode *t,visit v){
	stack *s=init_s();
	tnode *cur=t;
	while(cur || !isEmpty(s)){
		if(cur){
			push(s,cur);
			cur=cur->lchild;
		}else{
			cur=pop(s);
			v(cur);
			cur=cur->rchild;
		}
	}
}
void nopostorder(tnode *t,visit v){
	stack *s=init_s();
	tnode *cur=t;
	while(cur || !isEmpty(s)){
		if(cur){
			push(s,cur);
			cur=cur->lchild;
		}else{
			cur=(tnode*)getTop(s);
			if(cur->rchild && !cur->flag){
				cur->flag=1;
				cur=cur->rchild;
			}else{
				cur=pop(s);
				v(cur);
				cur=NULL;
			}
		}
	}
}

void createTree1(tnode **n,char*data,int* idx){
	char ch;
	ch=data[*idx];
	*idx+=1;
	if(ch == '#'){
		*n=NULL;		
	}else{
		*n=(tnode*)malloc(sizeof(tnode));
		(*n)->data=ch;
		(*n)->flag=0;
		createTree1(&(*n)->lchild,data,idx);
		createTree1(&(*n)->rchild,data,idx);
	}
}


void pn(tnode* n){
	if(n)
		printf("%c ",n->data);
}
int main(int argc,char **argv){
	tnode* t;
	int index=0;
	createTree1(&t,argv[1],&index);
	printf("preorder:");
	preorder(t,pn);
	printf("\n");
	printf("nopreorder:");
	nopreorder(t,pn);
	printf("\n");
	printf("nopreorder1:");
	nopreorder1(t,pn);
	printf("\n");

	printf("inorder:");
	inorder(t,pn);
	printf("\n");
	printf("noinorder:");
	noinorder(t,pn);
	printf("\n");
	printf("noinorder1:");
	noinorder1(t,pn);
	printf("\n");
	
	printf("postorder:");
	postorder(t,pn);
	printf("\n");
	printf("nopostorder:");
	nopostorder(t,pn);
	printf("\n");

	return 0;
}
